#include <stdint.h>/*uint32_t*/
#include <stdlib.h> /*size_t*/
#include <string.h>/*memset*/
#include "rabin_chunking.h"
#include "../destor.h"
#include "spooky_c.h"
#include "../jcr.h"
#include <openssl/sha.h>
#include <openssl/md5.h>

#define GSIZE32BIT  0xffffffffLL
#define SLIDE(m,fp,bufPos,buf) do{	\
	    unsigned char om;   \
	    u_int64_t x;	 \
		if (++bufPos >= size)  \
            bufPos = 0;				\
        om = buf[bufPos];		\
        buf[bufPos] = m;		 \
		fp ^= U[om];	 \
		x = fp >> shift;  \
		fp <<= 8;		   \
		fp |= m;		  \
		fp ^= T[x];	 \
}while(0)

#define STRAVG  63
#define STRMIN  ((STRAVG+1)/2)
#define STRMAX  ((STRAVG+1)*4)

typedef unsigned int UINT32;
typedef unsigned long long int UINT64;
//time_t backup_now;

UINT32 GEAR[256];

enum {
	size = 48
};
UINT64 fp;
int bufpos;
UINT64 U[256];
unsigned char buf[size];
int shift;
UINT64 T[256];
UINT64 poly;

char *eFiles[] = { ".pdf", ".rmv", "ra", ".bmp", ".vmem", ".vmdk", ".jpeg",
		".rmvb", ".exe", ".mtv", "\\Program Files", "C:\\" };

long int MiAi[256][2] =
{
5652377,  45673472, 24423617, 146512310, 16341615, 142364781, 
3526234, 1225434201,  654410,324130,  3124312, 359840125, 
35, 15254201,  61,41870,  212, 3340125, 
121, 44122, 551, 8431641, 610, 824311, 
367, 254201,  651,7632410,  319, 7540125, 
129, 115422, 551, 34431741, 633, 424311,
11, 31, 17,5, 23, 37,
71,97,37,241,247,257,
137,2391,431,831,2137,4313,
173, 3022467, 523, 4507221, 753, 6750467,
143, 412234, 372, 3174123, 637, 324123, 
821, 25420451, 107,31023,  423, 3512545, 
667, 1541242, 851, 843541741, 453, 3244311, 
964, 223401,  910,3233410,  223, 354012523, 
827,12322, 751, 843178741, 456, 438911, 
};

size_t _last_pos;
size_t _cur_pos;

unsigned int _num_chunks;

int NUMFEATURE = 4;

const char bytemsb[0x100] = { 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5,
		5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6,
		6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7,
		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, };

/***********************************************the rabin**********************************************/
static uint32_t fls32(UINT32 v) {
	if (v & 0xffff0000) {
		if (v & 0xff000000)
			return 24 + bytemsb[v >> 24];
		else
			return 16 + bytemsb[v >> 16];
	}
	if (v & 0x0000ff00)
		return 8 + bytemsb[v >> 8];
	else
		return bytemsb[v];
}

static uint32_t fls64(UINT64 v) {
	UINT32 h;
	if ((h = v >> 32))
		return 32 + fls32(h);
	else
		return fls32((UINT32) v);
}

UINT64 polymod(UINT64 nh, UINT64 nl, UINT64 d) {

	int k = fls64(d) - 1;
	int i;

	//printf ("polymod : k = %d\n", k);

	d <<= 63 - k;

	//printf ("polymod : d = %llu\n", d);
	//printf ("polymod : MSB64 = %llu\n", MSB64);

	if (nh) {
		if (nh & MSB64)
			nh ^= d;

		//printf ("polymod : nh = %llu\n", nh);

		for (i = 62; i >= 0; i--)
			if (nh & ((UINT64) 1) << i) {
				nh ^= d >> (63 - i);
				nl ^= d << (i + 1);

				//printf ("polymod : i = %d\n", i);
				//printf ("polymod : shift1 = %llu\n", (d >> (63 - i)));
				//printf ("polymod : shift2 = %llu\n", (d << (i + 1)));
				//printf ("polymod : nh = %llu\n", nh);
				//printf ("polymod : nl = %llu\n", nl);

			}
	}
	for (i = 63; i >= k; i--) {
		if (nl & (long long int) (1) << i)
			nl ^= d >> 63 - i;

		//printf ("polymod : nl = %llu\n", nl);

	}

	//printf ("polymod : returning %llu\n", nl);

	return nl;
}

void polymult(UINT64 *php, UINT64 *plp, UINT64 x, UINT64 y) {

	int i;

	//printf ("polymult (x %llu y %llu)\n", x, y);

	UINT64 ph = 0, pl = 0;
	if (x & 1)
		pl = y;
	for (i = 1; i < 64; i++)
		if (x & ((long long int) (1) << i)) {

			//printf ("polymult : i = %d\n", i);
			//printf ("polymult : ph = %llu\n", ph);
			//printf ("polymult : pl = %llu\n", pl);
			//printf ("polymult : y = %llu\n", y);
			//printf ("polymult : ph ^ y >> (64-i) = %llu\n", (ph ^ y >> (64-i)));
			//printf ("polymult : pl ^ y << i = %llu\n", (pl ^ y << i));

			ph ^= y >> (64 - i);
			pl ^= y << i;

			//printf ("polymult : ph %llu pl %llu\n", ph, pl);

		}
	if (php)
		*php = ph;
	if (plp)
		*plp = pl;

	//printf ("polymult : h %llu l %llu\n", ph, pl);

}

UINT64 append8(UINT64 p, unsigned char m) {
	return ((p << 8) | m) ^ T[p >> shift];
}

UINT64 slide8(unsigned char m) {
	unsigned char om;
	//printf("this char is %c\n",m);
	if (++bufpos >= size)
		bufpos = 0;
	om = buf[bufpos];
	buf[bufpos] = m;
	return fp = append8(fp ^ U[om], m);
}

UINT64 polymmult(UINT64 x, UINT64 y, UINT64 d) {

	//printf ("polymmult (x %llu y %llu d %llu)\n", x, y, d);

	UINT64 h, l;
	polymult(&h, &l, x, y);
	return polymod(h, l, d);
}

void calcT(UINT64 poly) {

	int j;
	UINT64 T1;

	//printf ("rabinpoly::calcT ()\n");

	int xshift = fls64(poly) - 1;
	shift = xshift - 8;
	T1 = polymod(0, (long long int) (1) << xshift, poly);
	for (j = 0; j < 256; j++) {
		T[j] = polymmult(j, T1, poly) | ((UINT64) j << xshift);

		//printf ("rabinpoly::calcT tmp = %llu\n", polymmult (j, T1, poly));
		//printf ("rabinpoly::calcT shift = %llu\n", ((UINT64) j << xshift));
		//printf ("rabinpoly::calcT xshift = %d\n", xshift);
		//printf ("rabinpoly::calcT T[%d] = %llu\n", j, T[j]);

	}

	//printf ("rabinpoly::calcT xshift = %d\n", xshift);
	//printf ("rabinpoly::calcT T1 = %llu\n", T1);
	//printf ("rabinpoly::calcT T = {");
	//for (i=0; i< 256; i++)
	//printf ("\t%llu \n", T[i]);
	//printf ("}\n");

}

void rabinpoly_init(UINT64 p) {
	poly = p;
	calcT(poly);
}

void window_init(UINT64 poly) {

	int i;
	UINT64 sizeshift;

	rabinpoly_init(poly);
	fp = 0;
	bufpos = -1;
	sizeshift = 1;
	for (i = 1; i < size; i++)
		sizeshift = append8(sizeshift, 0);
	for (i = 0; i < 256; i++)
		U[i] = polymmult(i, sizeshift, poly);
	memset((char*) buf, 0, sizeof(buf));
}

void windows_reset() {
	fp = 0;
	//memset((char*) buf,0,sizeof (buf));
	//memset((char*) chunk,0,sizeof (chunk));
}

void chunkAlg_init() {
	window_init(FINGERPRINT_PT);
	_last_pos = 0;
	_cur_pos = 0;
	windows_reset();
	_num_chunks = 0;
}

void gear_init(){
    char seed[32];
	int i,j;
	for(i = 0 ; i < 256; i++){
		for(j=0; j<32;j++){
			seed[j] = i;
		}
		GEAR[i] = 0;
		{
    		unsigned char digest[16];
    		MD5_CTX ctx;
 			MD5_Init(&ctx);
			MD5_Update(&ctx, seed, 32);
			MD5_Final(digest,&ctx);
			memcpy( &GEAR[i], digest, 7);
		}
	}
}

int rabin_chunk_data(unsigned char *p, int n) {

	UINT64 f_break = 0;
	UINT64 count = 0;
	UINT64 fp = 0;
	int i = 1, bufPos = -1;

	unsigned char om;
	u_int64_t x;

	unsigned char buf[128];
	memset((char*) buf, 0, 128);

	if (n <= destor.chunk_min_size)
		return n;
	else
		i = destor.chunk_min_size;
	while (i <= n) {

		SLIDE(p[i - 1], fp, bufPos, buf);
		if (destor.chunk_algorithm == CHUNK_RABIN) {
			if (((fp & (destor.chunk_avg_size - 1)) == BREAKMARK_VALUE
					&& i >= destor.chunk_min_size) || i >= destor.chunk_max_size
					|| i == n) {
				break;
			} else
				i++;
		} else if (destor.chunk_algorithm == CHUNK_NORMALIZED_RABIN) {
			if (i < destor.chunk_avg_size) {
				if (((fp & (destor.chunk_avg_size * 2 - 1))
						== BREAKMARK_VALUE && i >= destor.chunk_min_size)
						|| i >= destor.chunk_max_size || i == n) {
					break;
				} else
					i++;
			} else {
				if (((fp & (destor.chunk_avg_size / 2 - 1))
						== BREAKMARK_VALUE && i >= destor.chunk_min_size)
						|| i >= destor.chunk_max_size || i == n) {
					break;
				} else
					i++;
			}
		}
	}
	return i;
}

void super_feature(unsigned char* p, int n, struct superF* SF)
{
    int number = 3;
	UINT64 SFeature, Feature[124];
	UINT64 fingerprint = 0;
	int i=48, j, bufPos=-1, jj, ii;

	unsigned char om, Fbuf[256], *Tempbuf;   		
	unsigned char buf[128];
	memset ((char*) buf,0, 128);
	memset((char*)Feature, 0, sizeof(Feature));
    
	for(j = 48; j >= 2; j--){
		SLIDE(p[i-j], fingerprint, bufPos, buf);
	}

	while(i <= n)
	{
		SLIDE(p[i-1], fingerprint, bufPos, buf);
		for(jj=0; jj < number*NUMFEATURE; jj++)
		{
			SFeature = (MiAi[jj][0]*fingerprint + MiAi[jj][1]) & GSIZE32BIT; //&GSIZE32BIT;
			if(SFeature > Feature[jj]){
				Feature[jj] = SFeature;
 			}
		}
		i++;
 	}
    
    jj = 0;
    Tempbuf = (unsigned char*) (Feature + NUMFEATURE*jj);
    uint64_t temp_hash = spooky_hash64(Tempbuf, 16, 12345678);
	SF->sf1 = temp_hash;

    jj++;
    Tempbuf = (unsigned char*) (Feature + NUMFEATURE*jj);
	temp_hash = spooky_hash64(Tempbuf, 16, 12345678);
	SF->sf2 = temp_hash;

    jj++;
    Tempbuf = (unsigned char*) (Feature + NUMFEATURE*jj);
	temp_hash = spooky_hash64(Tempbuf, 16, 12345678);
	SF->sf3 = temp_hash;
    
	//printf("%s,%d:Supfeature[0]: %lld.\n",__FILE__,__LINE__, SF[0]);	
  	return ;
 }



void featureSorting(UINT64 *Features) {

	int i, j;  
    UINT64 tmp;  
    for(i = 0; i < 12; i++)  
    {
        for(j = 0; j < 12-i; j++){      
            if(*(Features+j) > *(Features+j+1)){
                tmp = *(Features+j);
                *(Features+j) = *(Features+j+1);
                *(Features+j+1) = tmp;
            }
        }
    }
}

 UINT64 featureSelecting(UINT64* features, int n, int featureType) {
	 int i;
	 UINT64 tempFeature = *(features);
	 if(featureType == 1) {
		 /* return the max feature */
		 for (i = 1; i < n; i++) {
			 if (tempFeature < *(features+i))
			 	tempFeature = *(features+i);
		 }
	 }
	else if (featureType == 2) {
		/* return the min feature */
		for (i = 1; i < n; i++) {
			 if (tempFeature > *(features+i))
			 	tempFeature = *(features+i);
		 }
	}
	return tempFeature;
 }

 void sisd_rabin_fixed(unsigned char* p, int n, struct superF* SF)
 {
	 int subregion_num, subregion_size = n/destor.super_feature_subregion_num;
	 UINT64 Feature[24];
	 UINT64 fingerprint;
	 int i, j, bufPos, jj, ii, endpos;
 
	 unsigned char om, Fbuf[256], *Tempbuf;
	 unsigned char buf[128];
	 memset ((char*) buf, 0, 128);
	 memset((char*)Feature, 0, sizeof(Feature));
	 
	 i = 48;
	 bufPos=-1;
	 fingerprint = 0;
	 endpos = 0;
 
	 for(j = 48; j >= 2; j--)
		 SLIDE(p[i-j], fingerprint, bufPos, buf);
 
	 for (subregion_num = 0, jj = 0; subregion_num < destor.super_feature_subregion_num;
									 subregion_num++, jj++) {
		 endpos += subregion_size;
		 if (endpos > n)
			 endpos = n;
		 
		 while (i < endpos) {
			 SLIDE(p[i-1], fingerprint, bufPos, buf);
			 if (fingerprint > Feature[jj])
				 Feature[jj] = fingerprint;
			 i++;
		 }
	 }
 
	/* grouping phase */
    if (destor.features_per_sf == 3)
        get_sketch_threefeature_per_sf(SF, Feature);
    else if (destor.features_per_sf == 4) {
		if (destor.enable_sort_features)
        	get_sketch_fourfeature_per_sf_sorted(SF, Feature);
		else
			get_sketch_fourfeature_per_sf(SF, Feature);
    }
    else {
        get_sketch_fivefeature_per_sf(SF, Feature);
    }
    
	//printf("%s,%d:Supfeature[0]: %lld.\n",__FILE__,__LINE__, SF[0]);	
  	return ;
 }

 void sisd_gear_fixed(unsigned char* p, int n, struct superF* SF)
  {
	  int subregion_num, subregion_size = n/destor.super_feature_subregion_num;
	  UINT64 Feature[24];
	  UINT64 fingerprint;
	  int i, j, bufPos, jj, ii, endpos;
  
	  unsigned char om, Fbuf[256], *Tempbuf;
	  unsigned char buf[128];
	  memset ((char*) buf, 0, 128);
	  memset((char*)Feature, 0, sizeof(Feature));
	  
	  i = 48;
	  bufPos=-1;
	  fingerprint = 0;
	  endpos = 0;
  
	  for(j = 48; j >= 2; j--)
		  SLIDE(p[i-j], fingerprint, bufPos, buf);
  
	  for (subregion_num = 0, jj = 0; subregion_num < destor.super_feature_subregion_num;
									  subregion_num++, jj++) {
		  endpos += subregion_size;
		  if (endpos > n)
			  endpos = n;
		  
		  while (i < endpos) {
			  //SLIDE(p[i-1], fingerprint, bufPos, buf);
			  fingerprint = (fingerprint<<1) + GEAR[p[i]];
			  if (fingerprint > Feature[jj])
				  Feature[jj] = fingerprint;
			  i++;
		  }
	  }
  
	 /* grouping phase */
	 if (destor.features_per_sf == 3)
		 get_sketch_threefeature_per_sf(SF, Feature);
	 else if (destor.features_per_sf == 4) {
		 if (destor.enable_sort_features)
			 get_sketch_fourfeature_per_sf_sorted(SF, Feature);
		 else
			 get_sketch_fourfeature_per_sf(SF, Feature);
	 }
	 else {
		 get_sketch_fivefeature_per_sf(SF, Feature);
	 }
	 
	 //printf("%s,%d:Supfeature[0]: %lld.\n",__FILE__,__LINE__, SF[0]);  
	 return ;
  }

 inline void get_sketch_threefeature_per_sf(struct superF* sketches, UINT64* features) {
 
	 uint64_t temp_hash;
	 UINT64 TempFeatures[3];
	 int feature_size = 3*sizeof(UINT64);
 
	 TempFeatures[0] = featureSelecting(features, 4, 1);
	 TempFeatures[1] = featureSelecting(features+4, 4, 1);
	 TempFeatures[2] = featureSelecting(features+8, 4, 1);
	 temp_hash = spooky_hash64((unsigned char*)TempFeatures, feature_size, 12345678);
	 sketches->sf1 = temp_hash;
 
	 TempFeatures[0] = featureSelecting(features, 4, 2);
	 TempFeatures[1] = featureSelecting(features+4, 4, 2);
	 TempFeatures[2] = featureSelecting(features+8, 4, 2);
	 temp_hash = spooky_hash64((unsigned char*)TempFeatures, feature_size, 12345678);
	 sketches->sf2 = temp_hash;

	 featureSorting(features);
	 TempFeatures[0] = *(features);
	 TempFeatures[1] = *(features+1);
	 TempFeatures[2] = *(features+2);
	 temp_hash = spooky_hash64((unsigned char*)TempFeatures, feature_size, 12345678);
	 sketches->sf3 = temp_hash;
 }
 
 inline void get_sketch_fourfeature_per_sf_sorted(struct superF* sketches, UINT64* features) {
	 uint64_t temp_hash;
	 UINT64 TempFeatures[4];
	 int feature_size = 4*sizeof(UINT64);
 
	 featureSorting(features);
	 TempFeatures[0] = *(features);
	 TempFeatures[1] = *(features+1);
	 TempFeatures[2] = *(features+2);
	 TempFeatures[3] = *(features+3);
	 temp_hash = spooky_hash64((unsigned char*)TempFeatures, feature_size, 12345678);
	 sketches->sf1 = temp_hash;

	 featureSorting(features);
	 TempFeatures[0] = *(features+4);
	 TempFeatures[1] = *(features+5);
	 TempFeatures[2] = *(features+6);
	 TempFeatures[3] = *(features+7);
	 temp_hash = spooky_hash64((unsigned char*)TempFeatures, feature_size, 12345678);
	 sketches->sf2 = temp_hash;

	 featureSorting(features);
	 TempFeatures[0] = *(features+8);
	 TempFeatures[1] = *(features+9);
	 TempFeatures[2] = *(features+10);
	 TempFeatures[3] = *(features+11);
	 temp_hash = spooky_hash64((unsigned char*)TempFeatures, feature_size, 12345678);
	 sketches->sf3 = temp_hash;
 }

 inline void get_sketch_fourfeature_per_sf(struct superF* sketches, UINT64* features) {
	 uint64_t temp_hash;
	 UINT64 TempFeatures[4];
	 int feature_size = 4*sizeof(UINT64);
 
	 //featureSorting(features);
	 TempFeatures[0] = *(features);
	 TempFeatures[1] = *(features+3);
	 TempFeatures[2] = *(features+6);
	 TempFeatures[3] = *(features+9);
	 temp_hash = spooky_hash64((unsigned char*)TempFeatures, feature_size, 12345678);
	 sketches->sf1 = temp_hash;

	 featureSorting(features);
	 TempFeatures[0] = *(features+1);
	 TempFeatures[1] = *(features+4);
	 TempFeatures[2] = *(features+7);
	 TempFeatures[3] = *(features+10);
	 temp_hash = spooky_hash64((unsigned char*)TempFeatures, feature_size, 12345678);
	 sketches->sf2 = temp_hash;

	 //featureSorting(features);
	 TempFeatures[0] = *(features+2);
	 TempFeatures[1] = *(features+5);
	 TempFeatures[2] = *(features+8);
	 TempFeatures[3] = *(features+11);
	 temp_hash = spooky_hash64((unsigned char*)TempFeatures, feature_size, 12345678);
	 sketches->sf3 = temp_hash;
 }
 
 inline void get_sketch_fivefeature_per_sf(struct superF* sketches, UINT64* features) {
	 uint64_t temp_hash;
	 UINT64 TempFeatures[5];
	 int feature_size = 5*sizeof(UINT64);
 
	 TempFeatures[0] = *(features);
	 TempFeatures[1] = *(features+3);
	 TempFeatures[2] = *(features+6);
	 TempFeatures[3] = *(features+9);
	 TempFeatures[4] = *(features+12);
	 temp_hash = spooky_hash64((unsigned char*)TempFeatures, feature_size, 12345678);
	 sketches->sf1 = temp_hash;
 
	 TempFeatures[0] = *(features+1);
	 TempFeatures[1] = *(features+4);
	 TempFeatures[2] = *(features+7);
	 TempFeatures[3] = *(features+10);
	 TempFeatures[4] = *(features+13);
	 temp_hash = spooky_hash64((unsigned char*)TempFeatures, feature_size, 12345678);
	 sketches->sf2 = temp_hash;
 
 	 TempFeatures[0] = *(features+2);
	 TempFeatures[1] = *(features+5);
	 TempFeatures[2] = *(features+8);
	 TempFeatures[3] = *(features+11);
	 TempFeatures[4] = *(features+14);
	 temp_hash = spooky_hash64((unsigned char*)TempFeatures, feature_size, 12345678);
	 sketches->sf3 = temp_hash;
 }
